The present invention relates generally to data communication networks and more particularly relates to a method for the automatic setup of the CRM Traffic management parameter in ATM networks.
Currently, there is a growing trend to make Asynchronous Transfer Mode (ATM) networking technology the base of future global communications. ATM has already been adopted as a standard for broadband communications by the International Telecommunications Union (ITU) and by the ATM Forum, a networking industry consortium.
ATM originated as a telecommunication concept defined by the Comite Consulatif International Telegraphique et Telephonique (CCITT), now known as the ITU, and the American National Standards Institute (ANSI) for carrying user traffic on any User to Network Interface (UNI) and to facilitate multimedia networking between high speed devices at multi-megabit data rates. ATM is a method for transferring network traffic, including voice, video and data, at high speed. Using this connection oriented switched networking technology centered around a switch, a great number of virtual connections can be supported by multiple applications through the same physical connection. The switching technology enables bandwidth to be dedicated for each application, overcoming the problems that exist in a shared media networking technology, like Ethernet, Token Ring and Fiber Distributed Data Interface (FDDI). ATM allows different types of physical layer technology to share the same higher layerxe2x80x94the ATM layer.
ATM uses very short, fixed length packets called cells. The first five bytes, called the header, of each cell contain the information necessary to deliver the cell to its destination. The cell header also provides the network with the ability to implement congestion control and traffic management mechanisms. The fixed length cells offer smaller and more predictable switching delays as cell switching is less complex than variable length packet switching and can be accomplished in hardware for many cells in parallel. The cell format also allows for multi-protocol transmissions. Since ATM is protocol transparent, the various protocols can be transported at the same time. With ATM, phone, fax, video, data and other information can be transported simultaneously.
ATM is a connection oriented transport service. To access the ATM network, a station requests a virtual circuit between itself and other end stations, using the signaling protocol to the ATM switch. ATM provides the User Network Interface (UNI) which is typically used to interconnect an ATM user with an ATM switch that is managed as part of the same network.
The current standard solution for routing in a private ATM network is described in Private Network to Network Interface (PNNI) Phase 0 and Phase 1 specifications published by the ATM Forum. The previous Phase 0 draft specification is referred to as the Interim Inter-Switch Signaling Protocol (IISP). The goal of the PNNI specifications is to provide customers of ATM network equipment multi-vendor interoperability.
The Interim Local Management Interface (ILMI) for the PNNI protocol specification provides an auto-port configuration capability. This capability functions to minimize manual configuration operations for PNNI ports of switches. The Phase 0 solution to auto-port configuration is based on hop by hop routing utilizing a xe2x80x98best matchxe2x80x99 scheme. The Phase 1 PNNI based solution is based on Open Shortest Path First (OSPF) with the additions necessary for ATM. This scheme is essentially a xe2x80x98source routingxe2x80x99 scheme whereby each node has basic knowledge of the structure of the entire network and uses this knowledge to build a complete path from the source to the destination. When a connection is to be set up from a source to a destination, the source sends out a SETUP message that has within it the address of the destination. Each ATM network node along the way reads the next node from the SETUP message and forwards the message to an appropriate next node. This continues until the SETUP message arrives at its destination.
In the IISP Phase 0 specification standard, the ATM nodes in the network route the signaling SETUP message hop by hop (i.e., node by node) using a xe2x80x98best matchxe2x80x99 scheme. ATM addresses are 20 bytes long but only 19 bytes can be used for routing purposes. According to the IISP Phase 0 standard, several prefixes of the ATM address for each link can be registered.
When a node (i.e., an ATM switch) needs to decide to which particular node to route the received SETUP message to, it compares the destination address with all the registered addresses for all of its ports. Only if an address prefix is found that fully matches the destination address can the destination address be considered for routing. After all the prefixes are compared, the prefix address that is the longest is used to determine the routing of the SETUP message. It is important to note that the standard does not require the transfer of any routing information between two neighboring nodes. In addition, the standard also does not permit the use of a TRANSIT NET ID parameter during the signaling phase, which can be used to route to a different routing domain.
A disadvantage of this scheme is that all the prefixes of all neighboring nodes must be registered manually on each of the respective ports. For example, if a port is disconnected from a neighbor and connected to a new neighbor, then the registered addresses must be manually changed in both nodes. This type of network can be termed an absolutely static network.
The components of the ATM header consist of the following fields. A generic flow control (GFC) field provides flow control; a virtual path identifier (VPI)/virtual channel identifier (VCI) field allows the network to associate a given cell with a given connection; a payload type identifier (PTI) field indicates whether the cell contains user information or management related data and is also used to indicate a network congestion state or for resource management (i.e., the EFCI state which is encoded in the PTI field); a cell loss priority (CLP) field indicates that cells with this bit set should be discarded before cells with the CLP bit clear; a header error check (HEC) field is used by the physical layer for detection and correction of bit errors in the cell header and is used for cell delineation.
The provisioning of an ATM network connection may include the specification of a particular class of service. The following list the various classes of service currently defined in ATM. Constant bit rate (CBR) defines a constant cell rate and is used for emulating circuit switching (e.g., telephone, video conferencing, television, etc.). Variable bit rate (VBR) allows cells to be sent at a variable bit rate. Real-time VBR can be used for interactive compressed video and non real-time can be used for multimedia e-mail.
Available bit rate (ABR) is designed for data traffic (e.g., file transfer traffic, etc.) and is the class service connected with resource management. The source is required to control its rate depending on the congestion state of the network. The users are allowed to declare a minimum cell rate, which is guaranteed to the virtual circuit by the network. ABR traffic responds to congestion feedback from the network.
Both switches and end stations in the network implement ABR. Binary switches monitor their queue lengths, set the PTI for congestion state (EFCI) in the cell headers, but do not deal with the computation of explicit rate feedback when congestion occurs.
Explicit rate switches compute the rate at which a source end station can transmit and place this information in the explicit rate field in the returning resource management cell. The destination sends one resource management cell for every N data cells transmitted. If the source does not receive a returning resource management cell, it decreases its allowed cell rate. This results in the source automatically reducing its rate in cases of extreme congestion.
In the case when the source receives a resource management cell, it checks the congestion indication flag (CI bit), after which the sending rate may be increased. If the flag is set, then the sending rate must be reduced. After this stage, the rate is set to the minimum of the above and the explicit rate field.
A fourth class of service, unspecified bit rate (UBR), is utilized by data applications that are not sensitive to cell loss or delay and want to use leftover capacity. During congestion, the cells are lost but the sources are not expected to reduce their cell rate.
Traffic management (TM) can be defined as the process by which the flow of cells from one device to another within the ATM network is controlled in order to allow for the greatest possible flow rate for the longest possible periods of time. ATM network congestion is defined as a state of network elements (e.g., switches, concentrators, etc.) in which the network is not able to meet the negotiated network performance objectives for the already established connections, resulting in lost cells. ATM layer congestion can be caused by unpredictable statistical fluctuation of traffic flows or fault conditions within the network. The purpose of traffic management is to ensure that users get their desired quality of service. During periods of heavy loads, when traffic cannot be predicted in advance, ensuring quality of service presents a problem. This is the reason congestion control is the most essential aspect of traffic management.
Traffic management refers to the set of actions taken by the network to avoid congested conditions. Congestion control refers to the set of actions taken by the network to minimize the intensity, spread and duration of congestion. These actions are triggered by congestion in one or more network elements. In general, the following traffic and congestion control functions are available within ATM networking.
The ATM standard defines a standard mechanism for the ATM network for indicating congestion states (e.g., setting the EFCI encoded in the cell header) and for indicating cell loss priority for selecting which cell to drop first in case congestion exists. Explicit forward congestion indication (EFCI) is a congestion notification mechanism that the ATM layer service user may make use of to improve the utility that can be derived from the ATM layer. A network element sets the EFCI in the cell header in an impending congested or already congested state. A congested network element can selectively discard cells explicitly identified as belonging to a non-compliant ATM connection and/or those cells with their CLP bit set. This is to protect cells without their CLP bit cleared from being discarded for as long as possible.
For ABR traffic, the ATM forum has defined a traffic management scheme that uses Resource Management (RM) cells to control the traffic rate through the network based in part on the EFCI mechanism defined previously. With reference to FIG. 1, a source end station (SES) 20 inserts forward RM cells into the ATM network 22. The destination end station (DES) 24, upon receiving these forward RM cells, turns them around and sends them back as backward RM cells.
In prior art implicit rate control, if there has been congestion on the forward path (recognized at the DES (FIG. 1) by the EFCI bits of the incoming data cells), a congestion field in the backward RM cell is marked (i.e. set to a xe2x80x981xe2x80x99). The SES 20 receives the backward RM cell and acts upon it. If the congestion field indicates congestion or if the RM cell is not returned, the sending rate is reduced. When the SES 20 receives a backward RM cell with the congestion field not indicating a congestion, it may increase the sending rate on that particular virtual circuit (VC).
Explicit rate control enhances the implicit rate control by adding an explicit rate field to the RM cell. In this field, the SES indicates the rate at which it would like to transmit. If an explicit rate switch exists in the VC route it may reduce the value in the explicit rate field in the backward RM cells in case of congestion. In this case (the example in FIG. 1) explicit rate for the SES is indicated. The SES upon receiving the RM cells, adjusts its sending rate according to the explicit rate fields.
A block diagram of a portion of a typical ATM edge device 12 (i.e. a device that resides on the outer border of an ATM network) is illustrated in FIG. 2. A data source 15 is 10 shown coupled to a cell generator and scheduler 14 which, in turn, is coupled to a cell data buffer 16 and a physical interface 18. Data source 15 may be any device or system that supplies data to be transported over the physical media, e.g., Token Ring, Ethernet, video conferencing, etc. The function of physical interface 18 is to couple transmit and receive data from the physical media to cell generator/scheduler and traffic management module 14. Cell data buffer 16 functions as a temporary holding memory until cell generator/scheduler and traffic management module 14 has finished processing cells. The module functions to transmit cells at the current transmit rate and modify the transmit rate in accordance with traffic management direction.
A diagram illustrating the fields and their positions in a standard Traffic Management RM cell is shown in FIG. 3. The cell format 40 is shown in increasing byte order starting with byte number one. The ATM header comprises bytes 1-5. The protocol ID comprises byte 6. Byte 7 comprises a direction (DR) bit (forward=0, backward=1), a BECN cell indicator (a 1 if switch generated), a congestion indication (CI) bit (a 1 if congestion present), a no increase (NI) bit (a 1 means do not increase rate), a request acknowledge (RA) bit and a 3 bit reserved field. The explicit cell rate (ER) comprises bytes 8-9. Bytes 10-11 comprise the current cell rate (CCR). Bytes 12-13 comprise the minimum cell rate (MCR). The queue length indicator (QL) comprises bytes 14-17. The sequence number (SN) (an integer number) comprises bytes 18-21. Bytes 22-51 and a portion of byte 52 are reserved. A CRC-10 field occupies the remainder of byte 52 and byte 53.
In order to implement traffic management functions and the handling of RM cells, a common prior art approach is to modify cell scheduler 14 to include traffic management functions. The disadvantage of this approach is that it is usually a complex and expensive process. In addition, if traffic management functions are to be incorporated into different cell schedulers, the process must be repeated for each one.
One of the drawbacks, however, of the ATM protocol is its complexity. The protocol requires the setup of numerous parameters prior to the operation of the network and prior to the establishment of each call connection. The Traffic Management mechanism utilizes transmission descriptors in the performance of its tasks. The descriptors comprise a plurality of parameters that characterize the transmission behavior of the SES and are described below.
The CRM parameter was previously known as the XRM parameter but is currently referred to now as the missing RM cell count or CRM parameter. The CRM field of the Traffic Management descriptor represents the missing RM-cell count that limits the number of forward RM cells that may be sent in the absence of received backward RM cells. In other words, the CRM parameter determines the number of RM cells that can be lost before the VC transmit rate is decreased. For example, if CRM equals 2 and RM cell #5 is about to be transmitted, but RM cells #3 and #4 have not been received yet, the VC transmit rate should be decreased since the RM cell #5 if sent could get lost due to congestion in the network.
Note that almost all the other Traffic Management descriptor parameters, e.g., Nrm, PCR, MCR, etc., can be set with a priori values, the CRM parameter, however, is strongly dependent on the network topology, i.e., number of hops, and the devices that are in use in the network. In the prior art, the setup of the CRM parameter utilizes the cooperation of one or more network elements during setup or, in the alternative, the CRM parameter is set a priori to a particular value. Note also that bad or incorrect tuning of the CRM parameter (either too high or too low) can lead to a major reduction in performance when using Traffic Management in ATM networks.
As another example, consider a call connection set up between a source end station and a destination end station over a path that comprises a large number of hops. Suppose CRM is set to a default value of 1 and the NRM field (the maximum number of cells a source may send for each forward RM cell) is set to a default value of 32. Data cells begin to be transmitted into the long VC. The transmitting source end finishes transmitting the 32 data cells and transmits the RM cell.
The source end station then examines its receiver waiting for the transmitted RM cell to return. Assume the transmitted RM cell is not received for a relatively long time due to long RTT (many hops) or due to congestion in the network The RM cell did not get lost but the RTT is too long. Since the CRM parameter is not set to a proper value, the source end station, in response to the long RTT, needlessly reduces the transmission rate that results in a reduction of performance.
One the other hand, if the CRM parameter is set to too big a value, it will be discovered too late that one or more RM cells were lost, which also leads to degradation of performance. Note that the Nrm parameter can be set to a value less than 32 for fast response to network congestion with the consequence that more RM cells are generated.
Note also that, in connection with the TBE parameter, some vendors do not implement the software option specified by the TBE parameter, thus the CRM parameter must be set a priori in these products.
The present invention is a method of measuring the round trip time (RTT) of a virtual circuit (VC) utilizing the Traffic Management mechanism of ATM and automatically setting up the CRM Traffic Management descriptor parameter accordingly. The CRM parameter is setup adaptively and individually for a particular VC in real time while traffic is flowing so as to achieve better performance of the network.
The invention comprises means for the determination of an estimate of the CRM parameter. The means comprises CRM calculation means, a database for storage of RM cell related information, including but not limited to, RM cell assigned sequence numbers, transmission times, reception times, etc., means for filtering the transmission and reception times.
Under normal operation, the transmitter in the source end station sends data packets over the ATM network to a destination end station. Periodically, RM cells are sent out to the destination end station and back.
The CRM calculator functions to track the transmission and reception of RM cells from the source end station. Every RM cell transmitted is given a unique sequence number. All RM cell transmission and reception events are recorded in the database. A filter functions to smooth the data recorded that is derived from RM cell transmission events, e.g., calculated round trip time (RTT). Similarly, the filter functions to smooth the data recorded that is derived from RM cell reception events. The filters may comprise Exponential Averaging Filters that are filters well known in the data communication arts.
Data recorded in the database include various RM cell statistics including but not limited to sequence numbers, time of transmission, time of reception, etc. Note that either filtered data, non-filtered data or both can be stored in and/or retrieved from the database. In determining an estimate for the CRM parameter, the CRM calculator utilizes the data previously stored in the database.
It is important to note that, in the prior art, the CRM parameter is initially set to                     CRM        =                  ⌈                      TBE            Nrm                    ⌉                                    (        1        )            
This initial CRM parameter is setup via negotiation with other network elements during the initial startup period. The method of the present invention has an advantage over the prior art in that it does not place any additional requirement on the DES and the network elements and is operative to adapt itself dynamically in real time.
In addition, in the prior art, after setting CRM initially, the CRM parameter remains as defined at startup. In the event there are major traffic load variations, the CRM parameter will typically not be optimum. The method of the present invention, however, functions to dynamically adjust the CRM on a continuous basis.
There is provided in accordance with the present invention a method for adapting the missing Resource Management (RM) cell count (CRM) parameter for a Virtual Circuit (VC) in a Traffic Management (TM) descriptor to the state of an Asynchronous Transfer Mode (ATM) network, the method comprising the steps of measuring the round trip time (RTT) value from a source end station (SES) to a destination end station (DES) and back and measuring the transmission time interval between consecutive transmissions, calculating an estimate for the CRM parameter utilizing the following equation:   current_CRM  =            linear_co      ⁢      _      ⁢      1        +          RTT_mul      ·              ⌈                  linear_co          ⁢          _          ⁢                      2            ·                          RTT_interval                              RM_Tx                ⁢                _interval                                                    ⌉            
wherein
curr_CRM is the current estimate of the CRM parameter, linear_coxe2x80x941 is a first linearity coefficient for adjusting the calculation of RM, linear_coxe2x80x942 is a second linearity coefficient for adjusting the calculation of RM, RTT_mul defines how much larger CRM should be relative to the calculated value, RTT_interval is the round trip time interval, RM_Tx_interval is the elapsed time between the transmission of N successive RM cells, wherein N is a positive integer.
The step of measuring the round trip time comprises the steps of setting a Sequence Number (SN) field of the RM cell to a unique value, transmitting the RM cell, recording the time of transmission of the RM cell in a database, receiving the RM cell some time later, recording the time of reception of the RM cell in the database and calculating the round trip time utilizing the time of transmission and the time of reception.
The step of measuring the round trip time comprises the steps of setting a field in the Function Specific Fields portion of an Operation and Maintenance (OAM) cell to a unique sequence number, transmitting the RM cell, recording the time of transmission of the RM cell in a database, receiving the RM cell some time later, recording the time of reception of the RM cell in the database and calculating the round trip time utilizing the time of transmission and the time of reception.
There is also provided in accordance with the present invention a method for adapting the missing Resource Management (RM) cell count (CRM) parameter for a Virtual Circuit (VC) in a Traffic Management (TM) descriptor to the state of an Asynchronous Transfer Mode (ATM) network, the method comprising the steps of measuring the round trip time (RTT) value from a source end station (SES) to a destination end station (DES) and back, measuring the transmission time interval between consecutive transmissions, filtering a plurality of the round trip time values utilizing an exponential averaging filter, calculating an estimate for the CRM parameter utilizing the following equation:   current_CRM  =            linear_co      ⁢      _      ⁢      1        +          RTT_mul      ·              ⌈                  linear_co          ⁢          _          ⁢                      2            ·                          RTT_interval                              RM_Tx                ⁢                _interval                                                    ⌉            
wherein
curr_CRM is the current estimate of the CRM parameter, linear_coxe2x80x941 is a first linearity coefficient for adjusting the calculation of RM, linear_coxe2x80x942 is a second linearity coefficient for adjusting the calculation of RM, RTT_mul defines how much larger CRM should be relative to the calculated value, RTT_interval is the round trip time interval filtered by the exponential averaging filter, RM_Tx_interval is the elapsed time between the transmission of N successive RM cells filtered by the exponential averaging filter, wherein N is an integer.
Further, there is provided in accordance with the present invention a method for adapting the missing Resource Management (RM) cell count (CRM) parameter for a Virtual Circuit (VC) in a Traffic Management (TM) descriptor to the state of an Asynchronous Transfer Mode (ATM) network, the method comprising the steps of measuring the round trip time (RTT) value from a source end station (SES) to a destination end station (DES) and back and measuring the transmission time interval between consecutive transmissions, calculating an estimate for the CRM parameter as a function of the following:
curr_CRM=ƒ(RTT_interval,RM_Tx_interval)
wherein
curr_CRM is the current estimate of the CRM parameter, RTT_interval is the round trip time interval, RM_Tx_interval is the elapsed time between the transmission of N successive RM cells, wherein N is an integer.